#define ElemType int

typedef struct ListNode List_Node;

int* majorityElement(int* nums, int numsSize, int* returnSize);

#include "common.h"

int main()
{
	return 0;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* majorityElement(int* nums, int numsSize, int* returnSize)
{
	int elem1 = 0, vote1 = 0,
		elem2 = 0, vote2 = 0;

	for (int i = 0; i < numsSize; i++) {
		int num = nums[i];
		if (vote1 && num == elem1)
			vote1++;
		else if (vote2 && num == elem2)
			vote2++;
		else if (!vote1)
			elem1 = num, vote1++;
		else if (!vote2)
			elem2 = num, vote2++;
		else
			vote1--, vote2--;
	}

	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < numsSize; i++) {
		int num = nums[i];
		if (vote1 && num == elem1)
			cnt1++;
		if (vote2 && num == elem2)
			cnt2++;
	}

	int ans = -1, size = 0, len = numsSize / 3;
	if (vote1 > 0 && cnt1 > len)
		ans = elem1, size++;
	if (vote2 > 0 && cnt2 > len)
		ans = elem2, size++;

	*returnSize = size;
	int* res = calloc(size, sizeof(int));
	if (size == 0)
		return res;
	else if (size == 1)
		res[0] = ans;
	else
		res[0] = elem1, res[1] = elem2;
	return res;
}
